package offer.zixing.chapter02;

import java.util.HashMap;
import java.util.Map;

/**
 * 和为k的子数组
 *
 * 题目：输入一个整数数组和一个整数k，请问数组中有多少个数字之和等于k的连续子数组？
 * 例如输入数组[1, 1, 1]，k的值为2，有2个连续子数组之和等于2。
 */
public class Test010 {
    public static void main(String[] args) {
        System.out.println(subarraySum(new int[]{1, 3, 4, 1, 2}, 7));
    }

    public static int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> sumToCount = new HashMap<>();
        sumToCount.put(0, 1);
        int sum = 0;
        int count = 0;
        for (int num : nums) {
            sum += num;
            count += sumToCount.getOrDefault(sum - k, 0);
            sumToCount.put(sum, sumToCount.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}
